package org.pupil.list.mergeTwoLists;

import org.pupil.list.IList;
import org.pupil.list.ListNode;

/**
 * @Description: 合并两个有序链表, leetcode：https://leetcode.cn/problems/merge-two-sorted-lists/description/
 * @Author: pupil
 * @Date: 2024/07/29 下午 3:55
 */
public class MergeTwoLists {

    /**
     *
     * 题目介绍：
     * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
     *
     * head1：3->5->9->10->null  cur2
     * head2：2->7->8->13->null  cur1
     *
     * 0. 2 < 3  head：2  cur1：7  cur2：3  pre：2  链表：2->null
     * 1. 3 < 7  cur1: 7  cur2：5  pre：3  链表：2->3->null
     * 2. 5 < 7  cur1：7  cur2：9  pre：5  链表：2->3->5->null
     * 3. 7 < 9  cur1：8  cur2：9  pre：7  链表：2->3->5->7->null
     * 4. 8 < 9  cur1：13  cur2：9  pre：8  链表：2->3->5->7->8->null
     * 5. 9 < 13  cur1：13  cur2：10  pre：9  链表：2->3->5->7->8->9->null
     * 6. 10 < 13  cur1：13  cur2：null  pre：10  链表：2->3->5->7->8->9->10->null
     * 7. cur2：null 结束循环  pre：13  链表：2->3->5->7->8->9->10->13->null
     * 最终结果：链表：2->3->5->7->8->9->10->13->null
     */
    public static ListNode mergeTwoLists(ListNode head1, ListNode head2) {
        // 那个链表为空就返回另一个链表
        if (head1 == null || head2 == null) {
            return head1 == null ? head2 : head1;
        }

        // 设置头节点，那个链表的头节点小那个为头节点
        ListNode head = head1.val <= head2.val ? head1 : head2;
        ListNode cur1 = head.next; // 标记头节点链表遍历的当前节点，设置头节点链表的下一节点
        ListNode cur2 = head == head1 ? head2 : head1; // 标记非头节点链表遍历的当前节点
        ListNode pre = head; // 标记挂好的节点的最后一个节点

        while (cur1 != null && cur2 != null) {
            if (cur1.val <= cur2.val) {
                pre.next = cur1;
                cur1 = cur1.next;
            } else {
                pre.next = cur2;
                cur2 = cur2.next;
            }
            pre = pre.next;
        }

        // 那个cur为空，就指向另一个cur
        pre.next = cur1 != null ? cur1 : cur2;

        return head;
    }

    public static void main(String[] args) {
        ListNode head1 = IList.get(new int[]{3, 5, 9, 10});
        ListNode head2 = IList.get(new int[]{2, 7, 8, 13});

        ListNode listNode = mergeTwoLists(head1, head2);
        IList.ergodic(listNode);
    }
}
